class Solution // 买卖股票最佳时机
{
public:
        int maxProfit(vector<int> &p)
        {
                if (p.size() == 0)
                        return 0;
                int n = p.size();
                vector<vector<int>> dp(n, vector<int>(2));
                dp[0][0] = -p[0]; // f买入，那么刚开始就是买了股票，利润就是亏的
                for (int i = 1; i < n; ++i)
                {
                        // dp[i][0]表示有股票，我i天手上有股票有两种情况 ： 1、我i-1天手上就有股票；2、我i-1天手上没有票，i天买的股票。取最大值
                        // dp[i][1]表示没有股票，我i天手上没有票也有两种情况 ： 1、我i-1天手上就没有股票；2、我i-1天手上有票，我把票卖了。取最大值

                        dp[i][0] = max(dp[i - 1][0], 0 - p[i]);
                        dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + p[i]);
                }
                // return max(dp[n-1][0],dp[n-1][1]);
                return dp[n - 1][1]; // dp[n-1][0]表示买入，都没有卖出去，不可能是利润最高
        }
};

class Solution // 买卖股票最佳时机II
{
public:
        int maxProfit(vector<int> &p)
        {
                if (p.size() == 0)
                        return 0;
                int n = p.size();
                vector<vector<int>> dp(n, vector<int>(2));
                dp[0][0] = -p[0];
                for (int i = 1; i < n; ++i)
                {
                        // dp[i][0]表示有股票，我i天手上有股票有两种情况 ： 1、我i-1天手上就有股票；2、我i-1天手上没有票，i天买的股票。取最大值
                        // dp[i][1]表示没有股票，我i天手上没有票也有两种情况 ： 1、我i-1天手上就没有股票；2、我i-1天手上有票，我第i天把票卖了。取最大值
                        // 因为我随时可以换出售票，所以我买票的钱可以从我前一天都利润得到，也就是【今天买股票的利润 = 昨天利润 - 今天的股票价格】
                        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - p[i]);
                        dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + p[i]);
                }
                // return max(dp[n-1][0],dp[n-1][1]);
                return dp[n - 1][1]; // dp[n-1][0]表示买入，都没有卖出去，不可能是利润最高
        }
};

class Solution // 买卖股票最佳时机含冷冻期
{
public:
        int maxProfit(vector<int> &p)
        {
                int n = p.size();
                vector<vector<int>> dp(n, vector<int>(3));
                dp[0][0] = -1 * p[0];
                for (int i = 1; i < n; ++i) // 0,1,2表示买入，可交易，冷冻期三种状态，i表示天数
                {
                        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - p[i]);
                        dp[i][1] = max(dp[i - 1][1], dp[i - 1][2]);
                        dp[i][2] = dp[i - 1][0] + p[i];
                }
                return max(dp[n - 1][1], dp[n - 1][2]); // dp[n][0]表示最后一天是买入状态，都没有卖出去，不可能是最大利润
        }
};